package com.lsa.iview.trees;

import java.io.BufferedWriter;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.Writer;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.Stack;
import java.util.TreeMap;

import org.apache.commons.io.IOUtils;

import com.lsa.helpers.ISimpleClosure;
import com.lsa.helpers.IntegerComparator;
import com.lsa.helpers.Pair;
import com.lsa.helpers.Utils;
import com.lsa.iview.lists.SingeLinkedList;
import com.lsa.iview.lists.SingeLinkedListUtils;
import com.lsa.iview.trees.BinaryTree.Node;

public final class BinaryTreeUtils {
	public static void inorder(Node<Integer> n, List<Integer> traversal) {
		if (n.getLeft() != null) inorder(n.getLeft(), traversal);
		traversal.add(n.getData());
		if (n.getRight() != null) inorder(n.getRight(), traversal);
	}
	
	public static void inorderIter(Node<Integer> node, List<Integer> traversal) {
		Stack<Pair<Integer, Node<Integer>>> stack = new Stack<>();
		stack.add(Pair.create(0, node));
		while(!stack.isEmpty()) {
			Pair<Integer, Node<Integer>> frame = stack.peek();
			Integer ip = frame.getFirst();
			Node<Integer> curNode = frame.getSecond();
			if (curNode == null || ip == 2){
				stack.pop();
				continue;
			}
			try{
				if (ip == 0) {
					stack.add(Pair.create(0, curNode.getLeft()));
					continue;
				}
				traversal.add(curNode.getData());
				stack.add(Pair.create(0, curNode.getRight()));
			}
			finally{
				frame.setFirst(ip + 1);
			}
		}
	}
	
	public static void preorder(Node<Integer> n, List<Integer> traversal) {
		if (n == null) {
			return;
		}
		traversal.add(n.getData());
		preorder(n.getLeft(), traversal);
		preorder(n.getRight(), traversal);
	}
	
	public static void preorderIter(Node<Integer> node, List<Integer> traversal) {
		Stack<Pair<Integer, Node<Integer>>> stack = new Stack<>();
		stack.add(Pair.create(0, node));
		while(!stack.isEmpty()) {
			Pair<Integer, Node<Integer>> frame = stack.peek();
			Integer ip = frame.getFirst();
			Node<Integer> curNode = frame.getSecond();
			if (curNode == null || ip == 2){
				stack.pop();
				continue;
			}
			try{
				if (ip == 0) {
					traversal.add(curNode.getData());
					stack.add(Pair.create(0, curNode.getLeft()));
					continue;
				}
				stack.add(Pair.create(0, curNode.getRight()));
			}
			finally{
				frame.setFirst(ip + 1);
			}
		}
	}
	
	public static void postorder(Node<Integer> n, List<Integer> traversal) {
		if (n == null) {
			return;
		}
		postorder(n.getLeft(), traversal);
		postorder(n.getRight(), traversal);
		traversal.add(n.getData());
	}
	
	public static void postorderIter(Node<Integer> node, List<Integer> traversal) {
		Stack<Pair<Integer, Node<Integer>>> stack = new Stack<>();
		stack.add(Pair.create(0, node));
		while(!stack.isEmpty()) {
			Pair<Integer, Node<Integer>> frame = stack.peek();
			Integer ip = frame.getFirst();
			Node<Integer> curNode = frame.getSecond();
			if (curNode == null){
				stack.pop();
				continue;
			}
			try{
				if (ip == 0) {
					stack.add(Pair.create(0, curNode.getLeft()));
					continue;
				}
				else if (ip == 1) {
					stack.add(Pair.create(0, curNode.getRight()));
					continue;
				}
				traversal.add(curNode.getData());
				stack.pop();
			}
			finally{
				frame.setFirst(ip + 1);
			}
		}
	}
	
	public static <E> File writeAsTgfToFile(BinaryTree<E> t, String pathname)
			throws IOException {
		return writeAsTgfToFile(t.getRoot(), pathname);
	}
	
	public static <E> File writeAsTgfToFile(Node<E> root, String pathname)
			throws IOException {
		File path = new File(pathname);
		path.getParentFile().mkdirs();
		try(BufferedWriter writer = new BufferedWriter(new FileWriter(path))){
			IOUtils.write(toTgf(root).getBytes(), writer);
		}
		return path;
	}
	
	public static <E> BinaryTree<E> createTree(Comparator<E> comparator, E... elems) {
		BinaryTree<E> t = new BinaryTree<E>(comparator);
		for (E e : elems) {
			t.insert(e);
		}
		return t;
	}
	
	public static BinaryTree<Integer> createRandomIntTree(int n, final int lower, final int upper){
		return createRandomTree(IntegerComparator.instance(), new IRandom<Integer>() {
			@Override
			public Integer random() {
				return Utils.random(lower, upper);
			}
		}, n);
	}
	
	public static <E> BinaryTree<E> createRandomTree(Comparator<E> comparator, IRandom<E> randomize, int n){
		BinaryTree<E> t = new BinaryTree<E>(comparator);
		for (int i = 0; i < n; i++) {
			t.insert(randomize.random());
		}
		return t;
	}
	
	public static interface IRandom<E> {
		E random();
	}
	
	public static interface IFactory<E> {
		E createFrom(String val);
	}
	
	/**
	 * Reads integer binary tree from the file
	 * @param f
	 * @return
	 * @throws FileNotFoundException
	 */
	public static BinaryTree<Integer> fromTgf(File f) throws FileNotFoundException {
		return fromTgf(new FileInputStream(f));
	}
	
	public static BinaryTree<Integer> fromTgf(InputStream in) {
		return fromTgf(IntegerComparator.instance(), new IFactory<Integer>() {
			@Override
			public Integer createFrom(String val) {
				return Integer.parseInt(val);
			}
		}, in);
	}
	
	/**
	 * Reads binary tree from input stream. <br><br>
	 * Node IDs separated from values by spaces. <br>
	 * Each edge must be marked 'L' or 'R' accordingly to denote whether it is left or right edge.<br><br>
	 * @param comparator - to compare values at nodes
	 * @param factory - to create values from strings
	 * @param in - input stream
	 * @return
	 */
	public static <E> BinaryTree<E> fromTgf(Comparator<E> comparator, IFactory<E> factory, InputStream in) {
		BinaryTree<E> t = new BinaryTree<E>(comparator);
		try(Scanner s = new Scanner(in)) {
			String line;
			boolean isNodeSection = true;
			Map<Integer,Node<E>> id2Node = new HashMap<Integer, BinaryTree.Node<E>>();
			Set<Integer> rootFinder = new HashSet<Integer>();
			Set<Integer> toIds = new HashSet<Integer>();
			while(s.hasNext()) {
				line = s.nextLine();
				line = line.trim();
				if (line.matches("\\s*#\\s*")) {
					isNodeSection = false;
					continue;
				}
				String[] parts = line.split("\\s+");
				if (isNodeSection) {
					Integer id = Integer.parseInt(parts[0]);
					Node<E> n = new Node<E>(factory.createFrom(parts[1]));
					id2Node.put(id, n);
				}
				else {
					Integer fromId = Integer.parseInt(parts[0]);
					rootFinder.add(fromId);
					Integer toId = Integer.parseInt(parts[1]);
					toIds.add(toId);
					Node<E> from = id2Node.get(fromId);
					Node<E> to = id2Node.get(toId);
					
					if ("L".equals(parts[2])) {
						from.setLeft(to);
					}
					else {
						from.setRight(to);
					}
				}
			}
			rootFinder.removeAll(toIds);
			int rootId = rootFinder.isEmpty()? id2Node.keySet().iterator().next() : rootFinder.iterator().next(); 
			t.insert(id2Node.get(rootId));
		}
		return t;
	}
	
	public static <E> String toTgf(BinaryTree<E> t) {
		return toTgf(t.getRoot());
	}
	
	public static <E> String toTgf(Node<E> root) {
		StringBuilder sb = new StringBuilder();
		
		List<Pair<Integer,E>> vertices = new ArrayList<>();
		List<EdgeData> edges = new ArrayList<>();
		toTgf(-1, root, vertices, edges);
		for (Pair<Integer, E> v : vertices) {
			sb.append(v.getFirst()).append(' ').append(v.getSecond());
			sb.append(IOUtils.LINE_SEPARATOR);
		}
		sb.append("#").append(IOUtils.LINE_SEPARATOR);
		for (EdgeData e : edges) {
			sb.append(e.from).append(' ').append(e.to).append(e.isLeft? " L" : " R");
			sb.append(IOUtils.LINE_SEPARATOR);
		}
		return sb.toString();
	}
	
	private static <E> int toTgf(int idSeed, Node<E> root, List<Pair<Integer,E>> vertices, List<EdgeData> edges) {
		if (root == null) {
			return idSeed;
		}
		
		Node<E> left = root.getLeft();
		Node<E> right = root.getRight();
		
		idSeed = toTgf(idSeed, left, vertices, edges);
		int leftId = idSeed;
		idSeed = toTgf(idSeed, right, vertices, edges);
		vertices.add(Pair.create(++idSeed, root.getData()));
		if (left != null) {
			edges.add(new EdgeData(idSeed, leftId, true));
		}
		if (right != null) {
			edges.add(new EdgeData(idSeed, idSeed-1, false));
		}
		return idSeed;
	}
	
	private static class EdgeData {
		int from;
		int to;
		boolean isLeft;
		
		public EdgeData(int from, int to, boolean isLeft) {
			this.from = from;
			this.to = to;
			this.isLeft = isLeft;
		}
	}
	
	public static <E> int maxDepth(BinaryTree<E> t) {
		return maxDepth(t.getRoot());
	}
	
	public static <E> int maxDepth(Node<E> root) {
		if (root == null) return 0;
		int leftDepth = maxDepth(root.getLeft());
		int rightDepth = maxDepth(root.getRight());
		return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
	}
	
	public static <E> E minValue(BinaryTree<E> t) {
		return minValue(t.getRoot());
	}
	
	public static <E> E minValue(Node<E> root) {
		Node<E> min = min(root);
		if (min == null) {
			return null;
		}
		return min.getData();
	}
	
	public static <E> Node<E> min(Node<E> root) {
		if (root == null) {
			return null;
		}
		Node<E> min = root;
		while(min.getLeft() != null) {
			min = min.getLeft();
		}
		return min;
	}
	
	public static <E> Node<E> min(BinaryTree<E> t) {
		return min(t.getRoot());
	}
	
	public static <E> E maxValue(BinaryTree<E> t) {
		return minValue(t.getRoot());
	}
	
	public static <E> E maxValue(Node<E> root) {
		Node<E> max = max(root);
		if (max == null) {
			return null;
		}
		return max.getData();
	}
	
	public static <E> Node<E> max(Node<E> root) {
		if (root == null) {
			return null;
		}
		Node<E> max = root;
		while(max.getRight() != null) {
			max = max.getRight();
		}
		return max;
	}
	
	public static <E> Node<E> max(BinaryTree<E> t) {
		return max(t.getRoot());
	}
	
	public static boolean hasRootToLeafSum(BinaryTree<Integer> t, int sum) {
		Node<Integer> root = t.getRoot();
		if (root == null) {
			return false;
		}
		return hasRootToLeafSum(root, sum);
	}
	
	/**
	 * Given a binary tree and a sum, return true if the tree has a root-to-leaf path such that adding up all the values
	 *	along the path equals the given sum. 
	 *
	 * @param n
	 * @param sum
	 * @return
	 */
	public static boolean hasRootToLeafSum(Node<Integer> n, int sum) {
		if (n == null) {
			return sum == 0;
		}
		sum = sum - n.getData();
		return hasRootToLeafSum(n.getLeft(), sum) || hasRootToLeafSum(n.getRight(), sum); 
	}
	
	public static <E> void enumerateRootToLeafPathes(Node<E> n, ISimpleClosure<LinkedList<Node<E>>> pathCallback) {
		enumerateRootToLeafPathes(n, new LinkedList<Node<E>>(), pathCallback);
	}

	public static <E> void enumerateRootToLeafPathes(Node<E> n, LinkedList<Node<E>> path, ISimpleClosure<LinkedList<Node<E>>> pathCallback) {
		if (n == null) {
			return;
		}
		path.add(n);
		try{
			if (n.getLeft() == null && n.getRight() == null) {
				pathCallback.invoke(path);
			}
			else {
				enumerateRootToLeafPathes(n.getLeft(), path, pathCallback);
				enumerateRootToLeafPathes(n.getRight(), path, pathCallback);
			}
		}
		finally{
			path.removeLast();
		}
	}
	
	public static <E> void mirror(Node<E> n) {
		if (n == null) {
			return;
		}
		
		Node<E> left = n.getLeft();
		mirror(left);
		Node<E> right = n.getRight();
		mirror(right);
		Node<E> tmp = left;
		n.setLeft(right);
		n.setRight(tmp);
	}
	
	public static void doubleTree(Node<Integer> n) {
		if (n == null) {
			return;
		}
		
		Node<Integer> left = n.getLeft();
		Node<Integer> newNode = new Node<Integer>(n.getData());
		newNode.setLeft(left);
		n.setLeft(newNode);
		doubleTree(left);
		doubleTree(n.getRight());
	}
	
	public static <E> boolean isSame(Comparator<E> c, Node<E> r1, Node<E> r2) {
		if (r1 == null) {
			return r2 == null;
		}
		
		if (r2 == null) {
			return false;
		}
		
		if (c.compare(r1.getData(), r2.getData()) != 0) {
			return false;
		}
		
		return isSame(c, r1.getLeft(), r2.getLeft()) && isSame(c, r1.getRight(), r2.getRight());
	}
	
	public static int countTrees(int arraySize) {
		if (arraySize <= 1) {
			return 1;
		}
		
		int count = 0;
		for (int i = 0; i < arraySize; i++) {
			count += countTrees(i) * countTrees(arraySize - 1 - i); 
		}
		return count;
	}
	
	public static <E> boolean isBst(Comparator<E> c, Node<E> t, E lower, E higher) {
		if (t == null) {
			return true;
		}

		E e = t.getData();
		if (c.compare(lower, e) <=0 && c.compare(e, higher) <=0) {
			return isBst(c, t.getLeft(), lower, e) && isBst(c, t.getRight(), e, higher);
		}
		else {
			return false;
		}
	}
	
	public static <E> boolean isBalanced(Node<E> n) {
        return height(n) + 1 > -1;
    }
    
    private static <E> int height(Node<E> r) {
    	if (r == null) {return -1;} // line 0
    	
    	int leftHeight = height(r.getLeft()); // line 1
    	int rightHeight = height(r.getRight()); // line 2
    	if (leftHeight == -2 || rightHeight == -2  || Math.abs(leftHeight - rightHeight) > 1) return -2; // line 3
    	return Math.max(leftHeight, rightHeight) + 1;
    }
	
	public static void writeBstInPreorder(Node<Integer> t, File path) throws IOException {
		try(BufferedWriter bw = new BufferedWriter(new FileWriter(path))) {
			Integer min = BinaryTreeUtils.minValue(t);
			bw.write(min.toString());
			bw.write(' ');
			Integer max = BinaryTreeUtils.maxValue(t);
			bw.write(max.toString());
			bw.write(' ');
			writeBstInPreorder(t, bw);
		}
	}
	
	public static void writeBstInPreorder(Node<Integer> t, Writer w) throws IOException {
		w.write(t.getData().toString());
		w.write(' ');
		if (t.getLeft() != null) {
			writeBstInPreorder(t.getLeft(), w);
		}
		if (t.getRight() != null) {
			writeBstInPreorder(t.getRight(), w);
		}
	}
	
	public static BinaryTree<Integer> readIntegerBstFromPreorder(File path) throws FileNotFoundException {
		try(final Scanner s = new Scanner(path)){
			int min = s.hasNextInt()? s.nextInt() : -1;
			int max = s.hasNextInt()? s.nextInt() : -1;
			
			BinaryTree<Integer> tree = new BinaryTree<>(IntegerComparator.instance());
			if (s.hasNext()) {
				readIntegerBstFromPreorder(s, tree.insert(s.nextInt()), null, min, max);
			}
			return tree;
		}
	}
	
	private static Integer readIntegerBstFromPreorder(Scanner s, Node<Integer> root, Integer value, int min, int max) {
		if (value == null) {
			if (s.hasNext()) {
				value = s.nextInt();
			}
		}
		
		if (value != null && min <= value && value <= root.getData()) {
			Node<Integer> child = new Node<Integer>(value);
			root.setLeft(child);
			value = readIntegerBstFromPreorder(s, child, null, min, root.getData());
		}
		
		if (value != null && root.getData() <= value && value <= max) {
			Node<Integer> child = new Node<Integer>(value);
			root.setRight(child);
			value = readIntegerBstFromPreorder(s, child, null, root.getData(), max);
		}
		
		return value;
	}
	
	public static BinaryTree<Integer> createRandomTree(int nodeCount, int min, int max) {
		BinaryTree<Integer> tree = new BinaryTree<>(IntegerComparator.instance());
		for (int i = 0; i < nodeCount; i++) {
			tree.insert(Utils.random(min, max));
		}
		return tree;
	}
	
	public static <E> Node<E> successor(Node<E> n) {
		if (n == null) {
			return null;
		}
		if (n.getRight() != null) {
			return min(n.getRight());
		}
		
		while(n.getParent() != null && n == n.getParent().getRight() ) {
			n = n.getParent();
		}
		
		return n.getParent();
	}
	
	public static <E> Node<E> predecessor(Node<E> n) {
		if (n == null) {
			return null;
		}
		if (n.getLeft() != null) {
			return max(n.getLeft());
		}
		
		while(n.getParent() != null && n == n.getParent().getLeft() ) {
			n = n.getParent();
		}
		
		return n.getParent();
	}
	
	public static <E> Iterator<E> reverseIterator(Node<E> root) {
		return iterator(root, true);
	}
	
	public static <E> Iterator<E> iterator(Node<E> root) {
		return iterator(root, false);
	}
	
	public static <E> Iterator<E> iterator(final Node<E> root, final boolean isReverse) {
		return new Iterator<E>(){
			private Node<E> n = root;
			
			@Override
			public boolean hasNext() {
				return n != null;
			}

			@Override
			public E next() {
				E e = n.getData();
				n = isReverse? BinaryTreeUtils.predecessor(n) : BinaryTreeUtils.successor(n);
				return e;
			}

			@Override
			public void remove() {
				throw new UnsupportedOperationException();
			}
		};
	}
	
	public static <E> BinaryTree<E> intersection(BinaryTree<E> t1, BinaryTree<E> t2) {
		Comparator<E> c = t1.getComparator();
		if (!Objects.equals(c, t2.getComparator())) {
			throw new IllegalArgumentException("Comparators not equal");
		}
		BinaryTree<E> r = new BinaryTree<E>(c);
		
		Iterator<E> i1 = t1.iterator();
		Iterator<E> i2 = t2.iterator();
		if (!i1.hasNext() || !i2.hasNext()){
			return r;
		}
		
		E e1 = i1.next();
		E e2 = i2.next();
		
		// main idea - to restore 'balance', i.e. when c.compare(e1, e2)==0. When this is in not the case -
		// skip elements in the iter causing disbalance.
		// When it is not possible (no more elements in one of the iters) - break out of the loop.
		while(true) {
			int cmp = c.compare(e1, e2);
			if (cmp < 0) {
				if (i1.hasNext()) {
					e1 = i1.next();
				}
				else{
					break;
				}
			}
			else if (cmp == 0) {
				r.insert(e1);
				if (i1.hasNext() && i2.hasNext()) {
					e1 = i1.next();
					e2 = i2.next();
				}
				else{
					break;
				}
				
			}
			else { // cmp > 0
				if (i2.hasNext()) {
					e2 = i2.next();
				}
				else{
					break;
				}
			}
		}		
		return r;
	}
	
	public static <E> BinaryTree<E> copy(BinaryTree<E> src, BinaryTree<E> dst) {
		if (!Objects.equals(src.getComparator(), dst.getComparator())) {
			throw new IllegalArgumentException("Comparators not equal");
		}
		Node<E> cpy = copy(src.getRoot());
		dst.insert(cpy);
		return dst;
	}
	
	public static <E> Node<E> copy(Node<E> src) {
		Node<E> cpy;
		if (src != null) {
			cpy = new Node<E>(src.getData());
			cpy.setLeft(copy(src.getLeft()));
			cpy.setRight(copy(src.getRight()));
		}
		else{
			cpy = null;
		}
		return cpy;
	}
	
	public static <E> BinaryTree<E> union(BinaryTree<E> t1, BinaryTree<E> t2) {
		Comparator<E> c = t1.getComparator();
		if (!Objects.equals(c, t2.getComparator())) {
			throw new IllegalArgumentException("Comparators not equal");
		}
		BinaryTree<E> r = new BinaryTree<E>(c);
		
		Iterator<E> i1 = t1.iterator();
		Iterator<E> i2 = t2.iterator();
		if (!i1.hasNext()){
			return copy(t2, r);
		}
		else if (!i2.hasNext()){
			return copy(t1, r);
		}
		
		E e1 = i1.next();
		E e2 = i2.next();
		while(true) {
			int cmp = c.compare(e1, e2);
			if (cmp < 0) { // first el is smaller
				r.insert(e1);
				if (i1.hasNext()) {
					e1 = i1.next();
				}
				else{
					r.insert(e2); // consume unconsumed (greater) el from the second iter
					break;
				}
			}
			else if (cmp == 0) {
				r.insert(e1);
				if (i1.hasNext() && i2.hasNext()) {
					e1 = i1.next();
					e2 = i2.next();
				}
				else{
					break;
				}
			}
			else { // cmp > 0 // second el is smaller
				r.insert(e2);
				if (i2.hasNext()) {
					e2 = i2.next();
				}
				else{
					r.insert(e1); // consume unconsumed (greater) el from the first iter
					break;
				}
			}
		}
		
		// append elements in the first iter to the result, if any. Here predicate holds : i1.hasNext() NAND i2.hasNext()  
		while(i1.hasNext()) {
			r.insert(i1.next());
		}
		
		// append elements in the second iter to the result, if any. Here predicate holds : i1.hasNext() NAND i2.hasNext()
		while(i2.hasNext()) {
			r.insert(i2.next());
		}

		return r;
	}
	
	public static <E> void connectNextRight(Node<WithNextRight<E>> root) {
		Node<WithNextRight<E>> firstNode = root; // first node in level
		Node<WithNextRight<E>> right = null; 
		while(firstNode != null) {
			Node<WithNextRight<E>> levelIter = firstNode;
			firstNode = firstNode.getLeft();
			while(levelIter != null) {
				Node<WithNextRight<E>> left = levelIter.getLeft();
				if (left == null) break;
				if (right != null) {
					right.getData().nextRight = left;
				}
				right = levelIter.getRight();
				left.getData().nextRight = right;
				levelIter = levelIter.getData().nextRight;
			}
			right = null;
		}
	}
	
	/**
	 * Recursive version of the {@link #connectNextRight}
	 * @param root
	 */
	public static <E> void connectNextRightRec(Node<WithNextRight<E>> root) {
		if (root == null) {
			return;
		}
		
		if (root.getLeft() != null) {
			root.getLeft().getData().nextRight = root.getRight(); 
		}
		
		if (root.getRight() != null) {
			Node<WithNextRight<E>> nextRight = root.getData().nextRight;
			if (nextRight != null) {
				root.getRight().getData().nextRight = nextRight.getLeft();
			}
		}
		
		connectNextRightRec(root.getLeft());
		connectNextRightRec(root.getRight());
	}
	
	public static <E> BinaryTree<WithNextRight<E>> createTreeWithNextRight(final Comparator<E> comparator, E... arr) {
		BinaryTree<WithNextRight<E>> tree = new BinaryTree<WithNextRight<E>>(new Comparator<WithNextRight<E>>() {
			@Override
			public int compare(WithNextRight<E> e1, WithNextRight<E> e2) {
				return comparator.compare(e1.data, e2.data);
			}
		});
		for (WithNextRight<E> e : arrayWithNextRight(arr)) {
			tree.insert(e);
		}
		return tree;
	}
	
	public static BinaryTree<WithNextRight<Integer>> createCompleteTreeWithNextRight(int power) {
		int nodesNum = (int)Math.pow(2, power) - 1;
		BinaryTree<WithNextRight<Integer>> t = new BinaryTree<WithNextRight<Integer>>(new Comparator<WithNextRight<Integer>>() {
			@Override
			public int compare(WithNextRight<Integer> e1, WithNextRight<Integer> e2) {
				return IntegerComparator.instance().compare(e1.data, e2.data);
			}
		});
		int mid = (nodesNum - 1) / 2;
		t.insert(new WithNextRight<Integer>(mid));
		createCompleteTreeWithNextRight(t.getRoot(), 0, nodesNum - 1);
		return t;
	}
	
	public static void createCompleteTreeWithNextRight(Node<WithNextRight<Integer>> root, int from, int to) {
		if (from < to) {
			int mid = from + ((to - from) >> 1);
			int leftMid = from + ((mid - 1 - from) >> 1);
			int rightMid = mid + 1 + ((to - 1 - mid) >> 1);
			Node<WithNextRight<Integer>> left = new Node<BinaryTreeUtils.WithNextRight<Integer>>(new WithNextRight<Integer>(leftMid));
			Node<WithNextRight<Integer>> right = new Node<BinaryTreeUtils.WithNextRight<Integer>>(new WithNextRight<Integer>(rightMid));
			root.setLeft(left);
			root.setRight(right);
//			System.out.println(String.format("[%s %s][%s %s]", from, mid - 1, mid + 1, to));
			createCompleteTreeWithNextRight(left, from, mid - 1);
			createCompleteTreeWithNextRight(right, mid + 1, to);
		}
	}
	
	public static BinaryTree<Integer> createCompleteTree(int power) {
		int nodesNum = (int)Math.pow(2, power) - 1;
		BinaryTree<Integer> t = new BinaryTree<Integer>(IntegerComparator.instance());
		int mid = (nodesNum - 1) / 2;
		t.insert(mid);
		createCompleteTree(t.getRoot(), 0, nodesNum - 1);
		return t;
	}
	
	public static void createCompleteTree(Node<Integer> root, int from, int to) {
		if (from < to) {
			int mid = from + ((to - from) >> 1);
			int leftMid = from + ((mid - 1 - from) >> 1);
			int rightMid = mid + 1 + ((to - 1 - mid) >> 1);
			Node<Integer> left = new Node<Integer>(leftMid);
			Node<Integer> right = new Node<Integer>(rightMid);
			root.setLeft(left);
			root.setRight(right);
			createCompleteTree(left, from, mid - 1);
			createCompleteTree(right, mid + 1, to);
		}
	}
	
	@SuppressWarnings("unchecked")
	public static <E> WithNextRight<E>[] arrayWithNextRight( E... arr ) {
		if (arr.length > 0) {
			WithNextRight<E> proto = new WithNextRight<E>(arr[0]);
			Object[] res = (Object[]) Array.newInstance(proto.getClass(), arr.length);
			res[0] = proto;
			for (int i = 1; i < arr.length; i++) {
				res[i] = new WithNextRight<E>(arr[i]);
			}
			return (WithNextRight<E>[]) res;	
		}
		else {
			return null;
		}
	}
	
	public static <E> Iterable<NodeWithLevel<E>> iterateLevels(final Node<E> root) {
		return new Iterable<NodeWithLevel<E>>() {
			Queue<Node<E>> queue = new LinkedList<Node<E>>();
			{
				queue.add(root);
			}
			int currentLevel = 0;
			int nodesInCurrentLevel = 1;
			int nodesInNextLevel = 0;
			@Override
			public Iterator<NodeWithLevel<E>> iterator() {
				return new Iterator<NodeWithLevel<E>>() {
					@Override
					public boolean hasNext() {
						return !queue.isEmpty();
					}

					@Override
					public NodeWithLevel<E> next() {
						Node<E> n = queue.poll();
						enqueue(n.getLeft());
						enqueue(n.getRight());
						int nodeLevel = currentLevel;
						if (--nodesInCurrentLevel == 0) {
							nodesInCurrentLevel = nodesInNextLevel;
							currentLevel++;
							nodesInNextLevel = 0;
						}
						return new NodeWithLevel<E>(n, nodeLevel);
					}
					
					private void enqueue(Node<E> n) {
						if (n != null) {
							queue.add(n);
							nodesInNextLevel++;
						}
					}

					@Override
					public void remove() {
						throw new UnsupportedOperationException();
					}
				};
			}
		};
	}
	
	public static <E> Iterable<NodeWithLevel<E>> iterateLevelsZigzag(final Node<E> root) {
		return new Iterable<NodeWithLevel<E>>() {
			int currentLevel = 0;
			
			Stack<Node<E>> stackOne = new Stack<Node<E>>();
			Stack<Node<E>> stackTwo = new Stack<Node<E>>();
			
			{
				stackOne.push(root);
			}
			
			@Override
			public Iterator<NodeWithLevel<E>> iterator() {
				return new Iterator<BinaryTreeUtils.NodeWithLevel<E>>() {
					@Override
					public boolean hasNext() {
						return !stackOne.isEmpty() || !stackTwo.isEmpty();
					}

					@Override
					public NodeWithLevel<E> next() {
						Node<E> n = null;
						
						if (stackOne.isEmpty()) {
							currentLevel++;
							swap();
						}
						
						n = stackOne.pop();
						if (currentLevel % 2 == 0) {
							saveChild(stackTwo, n.getLeft());
							saveChild(stackTwo, n.getRight());
						}
						else {
							saveChild(stackTwo, n.getRight());
							saveChild(stackTwo, n.getLeft());
						}
						
						return new NodeWithLevel<E>(n, currentLevel);
					}

					@Override
					public void remove() {
						throw new UnsupportedOperationException();
					}
				};
			}
			
			private void swap() {
				Stack<Node<E>> stackTmp = stackOne;
				stackOne = stackTwo;
				stackTwo = stackTmp; 
			}
			
			private void saveChild(Stack<Node<E>> s, Node<E> n) {
				if (n != null) s.push(n);
			}
		};
	}
	
	public static <E> String toString(Node<E> root) {
		class TreeCanvas implements ITreeCanvas {
			Map<Integer, StringBuilder> level2Buffer = new TreeMap<Integer, StringBuilder>();
			@Override
			public void print(int level, int offset, CharSequence txt) {
				StringBuilder buf = ensureBuffer(level, offset, txt);
				buf.replace(offset, offset+txt.length(), txt.toString());
			}
			
			private StringBuilder ensureBuffer(int level, int offset, CharSequence txt) {
				StringBuilder buf = level2Buffer.get(level);
				if (buf == null) {
					buf = new StringBuilder(padding(offset + txt.length()));
					level2Buffer.put(level, buf);
				}
				if (buf.length() < offset + txt.length()) {
					buf.append(padding(offset + txt.length() - buf.length()));
				}
				return buf;
			}
			
			private StringBuilder padding(int n){
				StringBuilder buf = new StringBuilder(n);
				for (int i = 0; i < n; i++) {
					buf.append(' ');
				}
				return buf;
			}
			
			String getText(){
				StringBuilder res = new StringBuilder(1024);
				for (StringBuilder buf : level2Buffer.values()) {
					res.append(buf).append(System.getProperty("line.separator"));
				}
				return res.toString();
			}
		}
		TreeCanvas canvas = new TreeCanvas();
		toStringInternal(root, 0, 0, canvas);
		return canvas.getText();
	}
	
	private static final int captionSize = 5;
	private static <E> Metrics toStringInternal(Node<E> root, int level, int offset, ITreeCanvas canvas) {
		Metrics m = new Metrics();
		if (root == null) {
			return m;
		}
		
		Metrics leftMetrics = toStringInternal(root.getLeft(), level + 1, offset, NullTreeCanvas.instance());
		String txt = centerPad(root.getData() != null? root.getData().toString() : "nul", captionSize);
		m.rootOffset = offset + leftMetrics.treeWidth;
		canvas.print(level, m.rootOffset, txt);
		Metrics rightMetrics = toStringInternal(root.getRight(), level + 1, offset + leftMetrics.treeWidth + txt.length(), NullTreeCanvas.instance());
		m.treeWidth = leftMetrics.treeWidth + txt.length() + rightMetrics.treeWidth;
		m.captionWidth = txt.length();
		
		harrow(m.rootOffset + txt.length() / 2, leftMetrics.rootOffset, level + 1, canvas);
		harrow(m.rootOffset + txt.length() / 2, rightMetrics.rootOffset, level + 1, canvas);
		
//		int newLevel = level + Math.max(m.rootOffset - leftMetrics.rootOffset, rightMetrics.rootOffset - m.rootOffset);
		int newLevel = level + 2;
		toStringInternal(root.getLeft(), newLevel, offset, canvas);
		toStringInternal(root.getRight(), newLevel, offset + leftMetrics.treeWidth + txt.length(), canvas);
		
		return m;
	}
	
	private static void harrow(int from, int to, int level, ITreeCanvas canvas) {
		if (to < 0) {
			return;
		}
		int i;
		to += captionSize/2;
		if (from < to) {
			for (i = from+1; i < to; i++) {
				canvas.print(level, i, "-");
			}
		} else {
			for (i = from-1; i > to; i--) {
				canvas.print(level, i, "-");
			}
		}
		canvas.print(level, i, "*");
	}
	
	private static void arrow(int from, int to, int level, ITreeCanvas canvas) {
		if (to < 0) {
			return;
		}
		
		if (from < to) {
			for (int i = from+1; i <= to; i++) {
				canvas.print(level++, i, "\\");
			}
		} else {
			for (int i = from-1; i >= to; i--) {
				canvas.print(level++, i, "/");
			}
		}
	}
	
	public static String rightPad(String s, int len) {
		StringBuilder sb = new StringBuilder();
		sb.append(s);
		int pad = (len - s.length());
		for (int i = 0; i < pad; i++) {
			sb.append('-');
		}
		return sb.toString();
	}
	
	public static String centerPad(String s, int len) {
		StringBuilder sb = new StringBuilder();
		int overallPad = (len - s.length());
		int leftPad = overallPad / 2;
		for (int i = 0; i < leftPad; i++) {
			sb.append(' ');
		}
		sb.append(s);
		for (int i = 0; i < overallPad - leftPad; i++) {
			sb.append(' ');
		}
		return sb.toString();
	}
	
	private static class Metrics {
		int treeWidth = 0;
		int captionWidth = 0;
		int rootOffset = -1;
	}
	
	private static interface ITreeCanvas {
		void print(int level, int offset, CharSequence txt);
	}
	
	private static class NullTreeCanvas implements ITreeCanvas{
		@Override
		public void print(int level, int offset, CharSequence txt) {
		}
		
		public static NullTreeCanvas instance() {
			return NullTreeCanvasHolder.INSTANCE;
		}
		
		private static class NullTreeCanvasHolder {
			static NullTreeCanvas INSTANCE = new NullTreeCanvas();
		}
	}
	
	public static <E> String printBorders(Node<E> root)  throws IOException {
		StringBuilder out = new StringBuilder();

		root = printListTree(root, out);
		printLeftBorder(root, out);
		printChildren(root, out);
		printRightBorder(root != null? root.getRight() : root, out);
		
		return out.toString();
	}
	
	private static <E> Node<E> printListTree(Node<E> root, Appendable out) throws IOException {
		while(root != null && (root.getLeft() == null || root.getRight() == null)) {
			out.append(root.getData().toString()+" ");
			if (root.getLeft() == null) {
				root = root.getRight();
			}
			else {
				root = root.getLeft();
			}
		}
		return root;
	}
	
	private static <E> void printLeftBorder(Node<E> root, Appendable out) throws IOException {
		if (root == null) {
			return;
		}
		
		if (root.getLeft() != null) {
			out.append(root.getData().toString()+" ");
			printLeftBorder(root.getLeft(), out);
		}
		else if (root.getRight() != null){
			out.append(root.getData().toString()+" ");
			printLeftBorder(root.getRight(), out);
		}
	}
	
	private static <E> void printChildren(Node<E> root, Appendable out) throws IOException {
		if (root == null) {
			return;
		}
		
		if (root.getLeft() == null && root.getRight() == null) {
			out.append(root.getData().toString()+" ");
		}
		else {
			printChildren(root.getLeft(), out);
			printChildren(root.getRight(), out);
		}
	}
	
	private static <E> void printRightBorder(Node<E> root, Appendable out) throws IOException {
		if (root == null) {
			return;
		}
		
		if (root.getRight() != null){
			printRightBorder(root.getRight(), out);
			out.append(root.getData().toString()+" ");
		}
		else if (root.getLeft() != null) {
			printRightBorder(root.getLeft(), out);
			out.append(root.getData().toString()+" ");
		}
	}
	
	/**
	 * Maximum subtree of the tree which is the BST
	 * @param root
	 * @param comparator
	 * @return
	 */
	public static <E> Node<E> maxBstRooted(Node<E> root, Comparator<E> comparator) {
		return maxBstRootedInner(root, comparator).maxBstRoot;
	}
	
	private static <E> MaxBstSubTreeInfo<E> maxBstRootedInner(Node<E> root, Comparator<E> comparator) {
		if (root == null) {
			return new MaxBstSubTreeInfo<E>();
		}
		
		MaxBstSubTreeInfo<E> infoLeft = maxBstRootedInner(root.getLeft(), comparator);
		MaxBstSubTreeInfo<E> infoRight = maxBstRootedInner(root.getRight(), comparator);
		
		if (infoLeft.isSubtreeBst() && infoRight.isSubtreeBst()
				&& (infoLeft.isEmpty() || comparator.compare(infoLeft.max, root.getData()) <= 0)
				&& (infoRight.isEmpty() || comparator.compare(root.getData(), infoRight.min) < 0)) {
			// reuse infoLeft
			infoLeft.maxBstRoot = root;
			infoLeft.min = !infoLeft.isEmpty() ? infoLeft.min : root.getData();
			infoLeft.max = !infoRight.isEmpty() ? infoRight.max : root.getData();
			infoLeft.maxBstNodeCount = infoLeft.nodeCount + infoRight.nodeCount + 1;
			infoLeft.nodeCount = infoLeft.maxBstNodeCount;
			return infoLeft;
		}
		
		MaxBstSubTreeInfo<E> res = infoRight;
		if (infoRight.maxBstNodeCount > infoLeft.maxBstNodeCount) {
			res = infoRight;
		}
		else {
			res = infoLeft;
		}
		res.nodeCount = infoLeft.nodeCount + 1 + infoRight.nodeCount;
		return res;
	}
	
	private static class MaxBstSubTreeInfo<E> {
		Node<E> maxBstRoot; // max BST root
		int maxBstNodeCount; // number of nodes in the BST
		E min;
		E max;
		
		int nodeCount; // number of nodes in the subtree
		
		public MaxBstSubTreeInfo() {
		}
		
		public boolean isSubtreeBst(){
			return nodeCount == maxBstNodeCount;
		}
		
		public boolean isEmpty() {
			return nodeCount == 0;
		}
	}
	
	public static <E> Node<E> maxBstWithRemovals(Node<E> root, Comparator<E> comparator) {
		return maxBstWithRemovalsInner(root, comparator).maxBstRoot;
	}
	
	private static <E> MaxBstSubTreeInfo<E> maxBstWithRemovalsInner(Node<E> root, Comparator<E> comparator) {
		if (root == null) {
			return new MaxBstSubTreeInfo<E>();
		}
		
		MaxBstSubTreeInfo<E> infoLeft = maxBstWithRemovalsInner(root.getLeft(), comparator);
		MaxBstSubTreeInfo<E> infoRight = maxBstWithRemovalsInner(root.getRight(), comparator);
		
		if (infoLeft.isSubtreeBst() && infoRight.isSubtreeBst()
				&& (infoLeft.isEmpty() || comparator.compare(infoLeft.max, root.getData()) <= 0)
				&& (infoRight.isEmpty() || comparator.compare(root.getData(), infoRight.min) < 0)) {
			// reuse infoLeft
			infoLeft.maxBstRoot = root;
			infoLeft.min = !infoLeft.isEmpty() ? infoLeft.min : root.getData();
			infoLeft.max = !infoRight.isEmpty() ? infoRight.max : root.getData();
			infoLeft.maxBstNodeCount = infoLeft.nodeCount + infoRight.nodeCount + 1;
			infoLeft.nodeCount = infoLeft.maxBstNodeCount;
			return infoLeft;
		}
		
		MaxBstSubTreeInfo<E> res = infoRight;
		if (infoRight.maxBstNodeCount > infoLeft.maxBstNodeCount) {
			res = infoRight;
		}
		else {
			res = infoLeft;
		}
		res.nodeCount = infoLeft.nodeCount + 1 + infoRight.nodeCount;
		return res;
	}
	
	public static BinaryTree<Integer> toBst(int[] arr) {
		Arrays.sort(arr);
		BinaryTree<Integer> t = new BinaryTree<Integer>(IntegerComparator.instance());
		t.insert(toBstInner(arr, 0, arr.length - 1));
		return t;
	}
	
	//   1 2 3 4 5 6 
	//   2 3 4 -> 2 + (4 - 2) / 2 -> 3
	//   2 3 4 5 -> 2 + (5 - 2) / 2 -> 3
	//   2 3 4 5 6 -> 2 + (6-2) /2 -> 4
	
	public static Node<Integer> toBstInner(int[] arr, int idxFrom, int idxTo) {
		if (idxFrom > idxTo) {
			return null;
		}
		int idxMid = idxFrom + (idxTo - idxFrom) / 2;
		Node<Integer> r = new Node<Integer>(arr[idxMid]);
		
		Node<Integer> left = toBstInner(arr, idxFrom, idxMid - 1);
		Node<Integer> right  = toBstInner(arr, idxMid + 1, idxTo);
		r.setLeft(left);
		r.setRight(right);
		
		return r;
	}
	
	public static BinaryTree<Integer> toBst(SingeLinkedList<Integer> l) {
		SingeLinkedListUtils.mergeSort(l, IntegerComparator.instance());
		
		BinaryTree<Integer> t = new BinaryTree<Integer>(IntegerComparator.instance());
//		if (!l.isEmpty()) {
//			SingeLinkedList.Node<Integer> last = null;
//			for (SingeLinkedList.Node<Integer> n = l.firstNode(); n != null; n = n.next) {
//				last = n;
//			}
//			t.insert(toBstInner(l.firstNode(), last));
//		}
		if (!l.isEmpty()) {
			@SuppressWarnings("unchecked")
			SingeLinkedList.Node<Integer>[] headPtr = (SingeLinkedList.Node<Integer>[])Array.newInstance(SingeLinkedList.Node.class, 1);
			headPtr[0] = l.firstNode();
			
			t.insert(toBstInner2(headPtr, 0, l.size()-1));
		}
		
		
		return t;
	}
	
	public static Node<Integer> toBstInner(SingeLinkedList.Node<Integer> from, SingeLinkedList.Node<Integer> to) {
		if (from == to) {
			return new Node<Integer>(from.data);
		}
		
		if (from.next == to) {
			Node<Integer> r = new Node<Integer>(from.data);
			r.setRight(new Node<Integer>(from.next.data));
			return r;
		}

		SingeLinkedList.Node<Integer> prevMiddle;
		SingeLinkedList.Node<Integer> middle;
		SingeLinkedList.Node<Integer> nextMiddle;
		
		SingeLinkedList.Node<Integer> prev = null;
		SingeLinkedList.Node<Integer> n = null, fast;
		for (n = from, fast = from; fast != to; ) {
			prev = n;
			n = n.next;
			fast = fast.next;
			if (fast != to) {
				fast = fast.next;
			}
		}
		prevMiddle = prev;
		middle = n;
		nextMiddle = middle.next;
		
		Node<Integer> r = new Node<Integer>(middle.data);
		r.setLeft(toBstInner(from, prevMiddle));
		r.setRight(toBstInner(nextMiddle, to));
		return r;
	}
	
	/**
	 * Faster version of {@link #toBstInner(com.lsa.iview.lists.SingeLinkedList.Node, com.lsa.iview.lists.SingeLinkedList.Node)}, with single list traversal
	 * 
	 * @param headPtr
	 * @param from
	 * @param to
	 * @return
	 */
	private static Node<Integer> toBstInner2(SingeLinkedList.Node<Integer>[] headPtr, int from, int to) {
		if (from > to) {
			return null;
		}
		
		int mid = (to + from) >>> 1;
		Node<Integer> left = toBstInner2(headPtr, from, mid - 1);
		Node<Integer> root = new Node<Integer>(headPtr[0].data);
		headPtr[0] = headPtr[0].next;
		Node<Integer> right = toBstInner2(headPtr, mid + 1, to);
		root.setLeft(left);
		root.setRight(right);
		return root;
	}
	
	/**
	 * Converts binary tree to the circular double-linked list in-place. <br><br>
	 * 
	 */
	public static Node<Integer> toDoubleLinkedList(Node<Integer> root) {
		if (root == null) {
			return null;
		}
		
		Node<Integer> left = toDoubleLinkedList(root.getLeft());
		Node<Integer> right = toDoubleLinkedList(root.getRight());
		
		root.setLeft(root);
		root.setRight(root);
		
		left = concat(left, root);
		left = concat(left, right);
		
		return left;
	}
	
	private static Node<Integer> concat(Node<Integer> first, Node<Integer> second) {
		if (first == null) {
			return second;
		}
		
		if (second == null) {
			return first;
		}
		
		Node<Integer> firstRight = first.getLeft();
		Node<Integer> secondRight = second.getLeft();
		
		second.setLeft(firstRight);
		firstRight.setRight(second);
		
		first.setLeft(secondRight);
		secondRight.setRight(first);
		
		return first;
	}
	
	/**
	 * Converts binary tree to the circular double-linked list in-place. <br><br>
	 * 
	 */
	@SuppressWarnings("unchecked")
	public static Node<Integer> toDoubleLinkedList2(Node<Integer> root) {
		Node<Integer>[] min = newArray(Node.class, 1);
		Node<Integer>[] max = newArray(Node.class, 1);
		
		if (root != null) {
			toDoubleLinkedListInner(root, min, max);
			// hard-wire the leftmost and end rightmost
			min[0].setLeft(max[0]);
			max[0].setRight(min[0]);
		}
		return min[0];
	}
	
	
	@SuppressWarnings("unchecked")
	private static void toDoubleLinkedListInner(Node<Integer> root, Node<Integer>[] min, Node<Integer>[] max) {
		Node<Integer>[] internalMin = newArray(Node.class, 1);
		Node<Integer>[] internalMax = newArray(Node.class, 1);
		
		if (root.getLeft() != null) {
			toDoubleLinkedListInner(root.getLeft(), internalMin, internalMax);
			root.setLeft(internalMax[0]);
			internalMax[0].setRight(root);
			min[0] = internalMin[0];
		}
		else {
			min[0] = root;
		}
		
		if (root.getRight() != null) {
			toDoubleLinkedListInner(root.getRight(), internalMin, internalMax);
			root.setRight(internalMin[0]);
			internalMin[0].setLeft(root);
			max[0] = internalMax[0];
		}
		else {
			max[0] = root;
		}
	}
	
	public static Node<Integer> lowestCommonAncestorInBst(Node<Integer> root, Node<Integer> n1, Node<Integer> n2) {
		if (root == null || n1 == null || n2 == null) {
			return null;
		}
		if (root.getData() > Math.max(n1.getData(), n2.getData())) {
			return lowestCommonAncestorInBst(root.getLeft(), n1, n2);
		}
		else if (root.getData() < Math.min(n1.getData(), n2.getData())) {
			return lowestCommonAncestorInBst(root.getRight(), n1, n2);
		}
		else {
			if (root.getData() != n1.getData() && root.getData() != n2.getData()) return root;
			else if (n1 == root || n2 == root) return root;
			
			return lowestCommonAncestorInBst(root.getLeft(), n1, n2);
		}
	}
	
	
	public static Node<Integer> lowestCommonAncestor(Node<Integer> r, Node<Integer> n1, Node<Integer> n2) {
		if (r == null) {
			return null;
		}
		if (r == n1 || r == n2) {
			return r;
		}
		
		Node<Integer> left = lowestCommonAncestor(r.getLeft(), n1, n2);
		Node<Integer> right = lowestCommonAncestor(r.getRight(), n1, n2);
		
		return left != null && right != null? r : left != null? left : right;
	}
	
	public static Node<Integer> lowestCommonAncestor2(Node<Integer> r, Node<Integer> n1, Node<Integer> n2) {
		List<Node<Integer>> dom1 = new ArrayList<BinaryTree.Node<Integer>>();
		List<Node<Integer>> dom2 = new ArrayList<BinaryTree.Node<Integer>>();
		
		Pair<Node<Integer>, Node<Integer>> n1n2 = lowestCommonAncestor2(r, n1, dom1, n2, dom2);
		if (n1n2.getFirst() != null || n1n2.getSecond() != null) {
			return null;
		}
		
		if (dom1.size() > dom2.size()) {
			List<Node<Integer>> tmp = dom1;
			dom1 = dom2;
			dom2 = tmp;
		}
		
		while(dom1.size() < dom2.size()) {
			dom2.remove(dom2.size() - 1);
		}
		
		while(dom1.size() > 0) {
			Node<Integer> d1 = dom1.remove(dom1.size() - 1);
			Node<Integer> d2 = dom2.remove(dom2.size() - 1);
			if (d1 == d2) {
				return d1;
			}
		}
		
		return null;
	}
	
	public static Node<Integer> lowestCommonAncestorUsingParent(Node<Integer> r, Node<Integer> n1, Node<Integer> n2) {
		Node<Integer> t = n1;
		int n1Depth = 0;
		while( t != r) {
			if (t == n2) {
				return n2;
			}
			n1Depth++;
			t = t.getParent();
		}
		
		// PRE: n2 is not the ancestor of the n1
		// PRE: n1_depth is the depth of the n1
		
		t = n2;
		int n2Depth = 0;
		while( t != r) {
			if (t == n1) {
				return n1;
			}
			n2Depth++;
			t = t.getParent();
		}
		
		// PRE: n1 is not the ancestor of the n2
		// PRE: n2_depth is the depth of the n2
		
		if (n1Depth > n2Depth) {
			t = n1;
			n1 = n2;
			n2 = t;
			
			int tmpN = n1Depth;
			n1Depth = n2Depth;
			n2Depth = tmpN;
		}
		
		while(n1Depth < n2Depth) {
			n2 = n2.getParent();
			n2Depth--;
		}
		
		// PRE: n1_depth == n2_depth
		while(n1Depth > 0) {
			n1 = n1.getParent();
			n2 = n2.getParent();
			n1Depth--;
			if (n1 == n2){ // LCA found
				return n1;
			}
		}
		
		return r;
	}
	
	private static Pair<Node<Integer>,Node<Integer>> lowestCommonAncestor2(Node<Integer> r, Node<Integer> n1, List<Node<Integer>> dom1, Node<Integer> n2, List<Node<Integer>> dom2) {
		if (n1 != null) {
			dom1.add(r);
		}
		
		if (n2 != null) {
			dom2.add(r);
		}
		
		if (r == n1) {
			n1 = null;
		}
		
		if (r == n2) {
			n2 = null;
		}
		
		Pair<Node<Integer>,Node<Integer>> n1n2 = Pair.create(n1, n2);
		
		if ((n1n2.getFirst() != null || n1n2.getSecond() != null) && r.getLeft() != null) {
			n1n2 = lowestCommonAncestor2(r.getLeft(), n1n2.getFirst(), dom1, n1n2.getSecond(), dom2);
		}
		
		if ((n1n2.getFirst() != null || n1n2.getSecond() != null) && r.getRight() != null) {
			n1n2 = lowestCommonAncestor2(r.getRight(), n1n2.getFirst(), dom1, n1n2.getSecond(), dom2);
		}
		
		if (n1n2.getFirst() != null) {
			dom1.remove(dom1.size() - 1);
		}
		
		if (n1n2.getSecond() != null) {
			dom2.remove(dom2.size() - 1);
		}
		
		return n1n2;
	}
	
	@SuppressWarnings("unchecked")
	private static <T> T[] newArray(Class<T> clazz, int size) {
		return (T[]) Array.newInstance(clazz, size);
	}
	
	public static class NodeWithLevel<E> {
		private Node<E> node;
		private int level;
		
		public NodeWithLevel(Node<E> node, int level) {
			this.node = node;
			this.level = level;
		}

		public Node<E> getNode() {
			return node;
		}

		public int getLevel() {
			return level;
		}
	}
	
	public static class WithNextRight<E> {
		private E data;
		private Node<WithNextRight<E>> nextRight;
		
		public WithNextRight(E data) {
			this.data = data;
		}
		
		public E getData() {
			return data;
		}

		public Node<WithNextRight<E>> getNextRight() {
			return nextRight;
		}

		@Override
		public String toString() {
			return String.format("[%s, nextRight=%s]", data,
					nextRight != null? nextRight.getData().data : "null");
		}
	}
	
	/**
	 * Static methods only
	 */
	private BinaryTreeUtils(){
	}
}

